#include"Heap.h"
void HPInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
void HPDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
void Swap(int* C, int* P)
{

	int tmp = *P;
	*P = *C;
	*C = tmp;
}
void AdjustUP(int* a,int Child)
{
	assert(a);
	int Parent = (Child - 1) / 2;
	while (Child > 0)
	{
		
		if (a[Child] < a[Parent])
		{
			Swap(&(a[Child]), &(a[Parent]));
		}
		else
		{
			break;
		}
		Child = (Child - 1) / 2;
		Parent = (Parent - 1) / 2;
	}
}
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUP(hp->a,hp->size);
}
void AdjustDown(HPDataType *a,int size,int parent)
{
	assert(a);
	int child = parent*2+1;
	while (child < size)
	{
		if (child + 1 < size && a[child] > a[child + 1])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(HP* hp)
{
	assert(hp);
	Swap(&(hp->a[hp->size]), &(hp->a[0]));
	hp->size--;
	AdjustDown(hp->a,hp->size,0);
}
HPDataType HeapTop(HP* hp)
{
	assert(hp);
	return hp->a[0];
}
int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}
bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}